import java.util.HashMap;
import java.util.Map;

public class Code2 {
    // 最长定差子序列

    // 首先使用的是最基本的动态规划的方式解决问题
    // 这个方法时间复杂度过大，超过了时间限制。但是思考和思维方式任然需要学习

    public int longestSubsequence1(int[] arr, int difference) {
        // 首先先创建出一个 dp 表
        // dp[i] 表示的是，以 i 位置的元素为结尾的所有子序列中，最长的等差子序列长度
        int n = arr.length;
        int[] dp = new int[n];

        // 初始化，将 dp 表中的元素初始化为最坏的情况。即，类似示例二只能为单个子元素
        for(int i = 0; i < n; i++){
            dp[i] = 1;
        }

        // 进行填表操作
        // 从左向右依次填写
        int ret = 1;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                // 此时需要判断 i位置的值 - j位置的值 是否符合 difference 的值
                if(arr[i] - arr[j] == difference){
                    dp[i] = dp[j] + 1;
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }

    // 第二种使用 hash 表的方式进行解决
    // 在 hash 表中实现动态规划，并进行了 记录 dp 表的操作，一个 for 循环解决问题减少了时间复杂度

    public int longestSubsequence2(int[] arr, int difference) {
        // 摒弃使用两个 for 循环实现动态规划
        // 这里会使用 hash 表的方式实现动态规划

        // 首先创建出一个 hash 表，在 hash 表中存放 dp 的值
        // dp[i] 表示的是，以 i 位置的元素为结尾的所有子序列中，最长的等差子序列长度
        // 在这里 前一个Integer 存储的是 key 即 arr[i]
        // 后一个 Integer 存储的是 value 即对应 dp[i]
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();

        // 定义一个变量，用来不断跟新最大的返回值
        int ret = 1;
        for(int a : arr){
            // getOrDefault 这个方法是针对找到值来确定返回值，找到返回前者，未找到返回 0
            // a - b = difference ，b = a - difference (这里的 b 就是 arr[a] 位置之前相关的值)
            // 这里将 a 与对应的 dp 值进行对应
            // 这里一句话解决了 三个问题
            // 1. 通过 for 循环保证了 a 元素始终是与 arr 数组中离自己最近的有效数关联
            // 2. 完成了 当 b 不存在是记录的数据为 1
            // 3. 实现了当找到与 a 相匹配的元素时，对应的 value 值 + 1
            hash.put(a, hash.getOrDefault(a - difference, 0) + 1);
            // 这里的 get(a) 获取到的是 a 所对应的 value 的值即 最长等差子序列
            ret = Math.max(ret, hash.get(a));
        }
        return ret;
    }
}
